"""
96. 不同的二叉搜索树
https://leetcode.cn/problems/unique-binary-search-trees/
"""
class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[0] = dp[1] = 1
        if n <= 1: return 1

        for i in range(2, n+1):
            curr = 0
            for j in range(i):
                l, r = j, i-j-1
                curr += dp[l]*dp[r]
            dp[i] = curr
        
        return dp[n]
